home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / exampleCode / games / IndiZone / gold / voxel.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  14.1 KB  |  613 lines
  1. /*
  2.  * The original copyright owners of the accompanying source code files have
  3.  * agreed to place such code into the public domain.  Accordingly, anyone
  4.  * who receives or obtains a copy of such source code is freely entitled to
  5.  * reproduce, use and otherwise exploit such code (including the right to
  6.  * make derivative works), at his/her own risk and expense, without any
  7.  * obligation or liability to the original copyright owners.
  8.  *
  9.  * We would appreciate (but do not require) that the following message be
  10.  * included in any derivative works:
  11.  *
  12.  * "Portions of this program were developed by Peter Broadwell, Rob Myers
  13.  * and Robin Schaufler while working in Silicon Valley."
  14.  *
  15.  * The accompanying source code files and related documentation materials
  16.  * are distributed on an "AS IS" basis, without any warranties or
  17.  * guarantees of any kind.  All implied warranties, including the implied
  18.  * warranties of merchantability and of fitness for any particular purpose,
  19.  * are expressly disclaimed.
  20.  */
  21. #include <stdio.h>
  22. #include "gl.h"
  23. #include "class.h"
  24. #include "classIds.h"
  25. #include "selectors.h"
  26. #include "mbox.h"
  27. #include "geom.h"
  28. #include "voxel.h"
  29.  
  30. #ifndef TRUE
  31. #define TRUE 1
  32. #endif
  33. #ifndef FALSE
  34. #define FALSE 0
  35. #endif
  36.  
  37. typedef struct {
  38.     int dim;
  39.     int dir;
  40. } dimdir;
  41.  
  42. extern class mboxClass;
  43.  
  44. voxel protovox;
  45. mailbox fullVoxels = {
  46.     &mboxClass,        /* myClass */
  47.     0, 0,        /* classFcns, nFcns */
  48.     /* mailbox */
  49.     0, 0,        /* *subscribers, *subscribedTo */
  50. };
  51.  
  52. extern voxel *clone();
  53.  
  54. char *dumpVoxel(), *voxtic();
  55.  
  56. fcnTable voxelFcns[] = {
  57.     DUMPVOX, dumpVoxel,
  58.     DOIT, voxtic,
  59.     EOTABLE
  60. };
  61.  
  62. class voxelClass = {
  63.     &mboxClass,    /* super, really mailbox */
  64.     voxelFcns,        /* fcnTable */
  65.     sizeof(voxel),
  66.     VOXEL
  67. };
  68.  
  69. voxel voxelTemplate = {
  70.     &voxelClass,    /* myClass */
  71.     0, 0,        /* classFcns, nFcns */
  72.             /*   mailbox */
  73.     0, 0,        /* *subscribers, *subscribedTo */
  74.             /*   voxel */
  75.     0, 0,        /* dim[0] */
  76.     0, 0,        /* dim[1] */
  77.     0, 0,        /* dim[2] */
  78.     0, 0, 0,        /* volume.orig */
  79.     0, 0, 0        /* volume.extent */
  80. };
  81.  
  82.     /*
  83.      *  these macros belong in geom.h.
  84.      */
  85. #define max_x(cube) (cube.orig.x + cube.extent.x)
  86. #define max_y(cube) (cube.orig.y + cube.extent.y)
  87. #define max_z(cube) (cube.orig.z + cube.extent.z)
  88.  
  89. #define half_up(num) (((num) + 1) / 2)
  90. #define in_interval(aval, orig, ext) \
  91.       ((aval) >= (orig) && (aval) < ((orig) + (ext)))
  92. /* #define abs(val) ((val) >= 0 ? (val) : -(val)) */
  93.  
  94.     /*
  95.      *  link prevvox ----> nextvox along linkdim.
  96.      */
  97. linkVoxels(prevvox, nextvox, linkdim)
  98.     voxel *prevvox, *nextvox;
  99.     int linkdim;
  100. {
  101.     voxel *tmpvox = NULL;
  102.     int curdim;
  103.  
  104.     nextvox->dim[linkdim][NEXT] = NULL;
  105.     prevvox->dim[linkdim][NEXT] = (inst *)nextvox;
  106.     nextvox->dim[linkdim][PREV] = (inst *)prevvox;
  107.     /* fill in other dimensions */
  108.     for(curdim = 0; curdim < NDIMENSIONS; curdim++) {
  109.     if(curdim == linkdim)
  110.         continue;
  111.         if(tmpvox = (voxel *)prevvox->dim[curdim][NEXT]) {
  112.             nextvox->dim[curdim][NEXT] = tmpvox->dim[linkdim][NEXT];
  113.             if(tmpvox = (voxel *)tmpvox->dim[linkdim][NEXT]) {
  114.             tmpvox->dim[curdim][PREV] = (inst *)nextvox;
  115.             }
  116.         } else {
  117.         nextvox->dim[curdim][NEXT] = NULL;
  118.     }
  119.         if(tmpvox = (voxel *)prevvox->dim[curdim][PREV]) {
  120.             nextvox->dim[curdim][PREV] = tmpvox->dim[linkdim][NEXT];
  121.             if(tmpvox = (voxel *)tmpvox->dim[linkdim][NEXT]) {
  122.             tmpvox->dim[curdim][NEXT] = (inst *)nextvox;
  123.             }
  124.         } else {
  125.         nextvox->dim[curdim][PREV] = NULL;
  126.         }
  127.     }
  128. }
  129.  
  130.     /*
  131.      *  Make a line of voxels headed by vox, in VOX_X dimension,
  132.      *  totalling universe_volume.x. Return vox.
  133.      */
  134.     voxel *
  135. makeLine(vox, universe_volume)
  136.     voxel *vox;
  137.     point *universe_volume;
  138. {
  139.     voxel *curvox = NULL, *newvox = NULL;
  140.     point relpos;
  141.  
  142.     if(vox == NULL || universe_volume == NULL)
  143.     return vox;
  144.     for(curvox = vox;
  145.     curvox &&
  146.         half_up(universe_volume->x) > max_x(curvox->volume);
  147.     curvox = (voxel *)curvox->dim[VOX_X][NEXT])
  148.     {
  149.     newvox = clone(curvox);
  150.     newvox->volume.orig.x += curvox->volume.extent.x;
  151.     linkVoxels(curvox, newvox, VOX_X);
  152.     relpos = newvox->volume.orig;
  153.  
  154.         /*
  155.          *  eventually, constrain targs < (universe/2) to be 0
  156.          *  and subtract (universe/2) from other targs.
  157.          */
  158. #define adj(targ,co) ((targ+(co)/2))
  159.     relpos.x = adj(relpos.x, newvox->volume.extent.x);
  160.     relpos.y = adj(relpos.y, newvox->volume.extent.y);
  161.     relpos.z = adj(relpos.z, newvox->volume.extent.z);
  162.     newvox->mbox.subscribers = NULL;
  163.     newvox->mbox.subscribedTo = NULL;
  164.     }
  165.     return vox;
  166. }
  167.  
  168.     /*
  169.      *  Make a plane of voxels headed by vox, in VOX_X,VOX_Y dimensions,
  170.      *  totalling universe_volume.[x,y]. Return vox.
  171.      */
  172.     voxel *
  173. makePlane(vox, universe_volume)
  174.     voxel *vox;
  175.     point *universe_volume;
  176. {
  177.     voxel *curvox = NULL, *newvox = NULL;
  178.  
  179.     if(vox == NULL || universe_volume == NULL)
  180.     return vox;
  181.     makeLine(vox, universe_volume);
  182.     for(curvox = vox;
  183.     curvox &&
  184.         half_up(universe_volume->y) > max_y(curvox->volume);
  185.     curvox = newvox)
  186.     {
  187.     newvox = clone(curvox);
  188.     newvox->volume.orig.y += curvox->volume.extent.y;
  189.     linkVoxels(curvox, newvox, VOX_Y);
  190.     makeLine(newvox, universe_volume);
  191.     }
  192.     return vox;
  193. }
  194.  
  195.     /*
  196.      *  Make a space of voxels headed by vox, in VOX_X,VOX_Y,VOX_Z
  197.      *  dimensions, totalling universe_volume.[x,y,z]. Return vox.
  198.      */
  199.     voxel *
  200. makeSpace(vox, universe_volume)
  201.     voxel *vox;
  202.     point *universe_volume;
  203. {
  204.     voxel *curvox = NULL, *newvox = NULL;
  205.  
  206.     if(vox == NULL || universe_volume == NULL)
  207.     return vox;
  208.     makePlane(vox, universe_volume);
  209.     for(curvox = vox;
  210.     curvox &&
  211.         half_up(universe_volume->z) > max_z(curvox->volume);
  212.     curvox = newvox)
  213.     {
  214.     newvox = clone(curvox);
  215.     newvox->volume.orig.z += curvox->volume.extent.z;
  216.     linkVoxels(curvox, newvox, VOX_Z);
  217.     makePlane(newvox, universe_volume);
  218.     }
  219.     return vox;
  220. }
  221.  
  222. compileVox()
  223. {
  224.     makeobj(1027);
  225.     fishColor(WHITE);
  226.     pushmatrix();
  227.     scale((float)protovox.volume.extent.x,
  228.       (float)protovox.volume.extent.y,
  229.       (float)protovox.volume.extent.z);
  230.     movei(0,0,0);
  231.     drawi(1,0,0);
  232.     drawi(1,1,0);
  233.     drawi(0,1,0);
  234.     drawi(0,1,1);
  235.     drawi(1,1,1);
  236.     drawi(1,0,1);
  237.     drawi(0,0,1);
  238.     popmatrix();
  239.     closeobj();
  240. }
  241.  
  242.     /*
  243.      *  The big bang creates the 3D universe of
  244.      *  voxels to fill universe_volume.
  245.      *  final universe may exceed universe_volume
  246.      *  by a fraction of a voxel.volume if
  247.      *  voxel_volume doesn't divide evenly into
  248.      *  universe_volume.
  249.      */
  250.     voxel *
  251. bigBang(universe_volume, voxel_volume)
  252.     point *universe_volume, *voxel_volume;
  253. {
  254.     voxel *vox, *clone();
  255.  
  256.     if(universe_volume == NULL || voxel_volume == NULL)
  257.     return NULL;
  258.     vox = clone(&voxelTemplate);
  259.     vox->volume.extent = *voxel_volume;
  260.     protovox = *vox;    /* debugging */
  261.     vox->volume.orig.x = -universe_volume->x / 2;
  262.     vox->volume.orig.y = -universe_volume->y / 2;
  263.     vox->volume.orig.z = -universe_volume->z / 2;
  264.  
  265.     /* for debugging */
  266.     compileVox();
  267.     Expand(&fullVoxels);
  268.  
  269.     makeSpace(vox, universe_volume);
  270.     return vox;
  271. }
  272.  
  273.     char *
  274. voxtic(vox)
  275.     voxel *vox;
  276. {
  277.     return (char *)vox;
  278. }
  279.  
  280.     char *
  281. drawVoxel(vox)
  282.     voxel *vox;
  283. {
  284.     register subscr *entry = NULL;
  285.     char tag[20], *tagp = tag;
  286.  
  287.     if(vox == NULL) {
  288.     fprintf(stderr, "drawVoxel: voxel is NULL\n");
  289.     return NULL;
  290.     }
  291.     if((entry = vox->mbox.subscribers) == NULL) {
  292. /*    return NULL;
  293. /* */
  294.     }
  295.     pushmatrix();
  296.     translate((float)vox->volume.orig.x,
  297.           (float)vox->volume.orig.y,
  298.           (float)vox->volume.orig.z);
  299.     /*
  300.      *  counteract effect of rotating the fishbowl
  301.      */
  302.     rotate(-900, 'y');
  303.     for(; entry; entry = entry->next) {
  304.     if(entry->member && entry->member->myClass) {
  305.             sprintf(tagp, "%d ", entry->member->myClass->classId);
  306.         tagp += strlen(tagp);
  307.     }
  308.     }
  309.     callobj(1027);
  310.     cmovi(0,0,0);
  311.     charstr(tag);
  312.     popmatrix();
  313.     return NULL;
  314. }
  315.  
  316.     char *
  317. dumpVoxel(vox)
  318.     voxel *vox;
  319. {
  320.     if(vox == NULL) {
  321.     fprintf(stderr, "dumpVoxel: voxel is NULL\n");
  322.     return NULL;
  323.     }
  324.     fprintf(stderr,"[%d,%d,%d]",
  325.     vox->volume.orig.x,
  326.     vox->volume.orig.y,
  327.     vox->volume.orig.z);
  328.     return NULL;
  329. }
  330.  
  331.     char *
  332. dumpLine(vox)
  333.     voxel *vox;
  334. {
  335.     voxel *curvox;
  336.  
  337.     if(vox == NULL) {
  338.     fprintf(stderr, "dumpLine: voxel is NULL\n");
  339.     return NULL;
  340.     }
  341.     for(curvox = vox; curvox; curvox = (voxel *)curvox->dim[VOX_X][NEXT]) {
  342.     dumpVoxel(curvox);
  343.     if(curvox->dim[VOX_X][NEXT] == NULL) {
  344.         fprintf(stderr, "\n");
  345.     } else if(((voxel *)curvox->dim[VOX_X][NEXT])->dim[VOX_X][PREV]
  346.               != (inst *)curvox)
  347.     {
  348.         fprintf(stderr, ">");
  349.     } else {
  350.         fprintf(stderr, " ");
  351.     }
  352.     }
  353.     return NULL;
  354. }
  355.  
  356.     char *
  357. dumpPlane(vox)
  358.     voxel *vox;
  359. {
  360.     voxel *curvox;
  361.  
  362.     if(vox == NULL) {
  363.     fprintf(stderr, "dumpLine: voxel is NULL\n");
  364.     return NULL;
  365.     }
  366.     for(curvox = vox; curvox; curvox = (voxel *)curvox->dim[VOX_Y][NEXT]) {
  367.     dumpLine(curvox);
  368.     }
  369.     return NULL;
  370. }
  371.  
  372.     char *
  373. dumpSpace(vox)
  374.     voxel *vox;
  375. {
  376.     voxel *curvox;
  377.  
  378.     if(vox == NULL) {
  379.     fprintf(stderr, "dumpLine: voxel is NULL\n");
  380.     return NULL;
  381.     }
  382.     for(curvox = vox; curvox; curvox = (voxel *)curvox->dim[VOX_Z][NEXT]) {
  383.     dumpPlane(curvox);
  384.     if(curvox->dim[VOX_Z][NEXT])
  385.         fprintf(stderr,"\n");
  386.     else
  387.         fprintf(stderr,"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
  388.     }
  389.     return NULL;
  390. }
  391.  
  392. pointInCube(aCube, aPoint)
  393.     cube *aCube;
  394.     point *aPoint;
  395. {
  396.     if(!aCube || !aPoint)
  397.     return FALSE;
  398.     return (in_interval(aPoint->x, aCube->orig.x, aCube->extent.x) &&
  399.         in_interval(aPoint->y, aCube->orig.y, aCube->extent.y) &&
  400.         in_interval(aPoint->z, aCube->orig.z, aCube->extent.z));
  401. }
  402.  
  403.     /*
  404.      *  Given a voxel and a point, find the voxel containing that point.
  405.      *  If pt is outside the universe, find the voxel nearest to it.
  406.      */
  407.     voxel *
  408. findvox(vox, pt)
  409.     voxel *vox;
  410.     point *pt;
  411. {
  412.     int dir = STATION;
  413.  
  414.     if(pt->x < vox->volume.orig.x) {
  415.     dir = PREV;
  416.     } else if(pt->x >= vox->volume.orig.x + vox->volume.extent.x) {
  417.     dir = NEXT;
  418.     } else dir = STATION;
  419.     if(dir != STATION) {
  420.     for(; vox && vox->dim[VOX_X][dir];
  421.           vox = (voxel *)vox->dim[VOX_X][dir]) {
  422.         if(in_interval(pt->x, vox->volume.orig.x, vox->volume.extent.x))
  423.         break;
  424.     }
  425.     }
  426.     if(pt->y < vox->volume.orig.y) {
  427.     dir = PREV;
  428.     } else if(pt->y >= vox->volume.orig.y + vox->volume.extent.y) {
  429.     dir = NEXT;
  430.     } else dir = STATION;
  431.     if(dir != STATION) {
  432.     for(; vox && vox->dim[VOX_Y][dir];
  433.           vox = (voxel *)vox->dim[VOX_Y][dir]) {
  434.         if(in_interval(pt->y, vox->volume.orig.y, vox->volume.extent.y))
  435.         break;
  436.     }
  437.     }
  438.     if(pt->z < vox->volume.orig.z) {
  439.     dir = PREV;
  440.     } else if(pt->z >= vox->volume.orig.z + vox->volume.extent.z) {
  441.     dir = NEXT;
  442.     } else dir = STATION;
  443.     if(dir != STATION) {
  444.     for(; vox && vox->dim[VOX_Z][dir];
  445.           vox = (voxel *)vox->dim[VOX_Z][dir]) {
  446.         if(in_interval(pt->z, vox->volume.orig.z, vox->volume.extent.z))
  447.         break;
  448.     }
  449.     }
  450.     return vox;
  451. }
  452.  
  453.     /*
  454.      *  Unsubscribe from vox;  find the voxel containing newpos;
  455.      *  subscribe to it, and return it.
  456.      */
  457.     voxel *
  458. newVoxPosition(vox, newpos, indiv)
  459.     voxel *vox;
  460.     point *newpos;
  461.     inst *indiv;
  462. {
  463.     voxel *newvox;
  464.     subscr *entry, *findvars();
  465.  
  466.     if(!vox || !newpos || !indiv)
  467.     return vox;
  468.     entry = findvars(indiv, VOXEL);
  469.     if(pointInCube(&vox->volume, newpos) && entry
  470.           && entry->member == (inst *)vox) {
  471.     return vox;
  472.     }
  473.     unsubscribe(vox, indiv);
  474.     if(!vox->mbox.subscribers)
  475.     unsubscribe(&fullVoxels, vox);
  476.     if(newvox = findvox(vox, newpos)) {
  477.     if(!newvox->mbox.subscribers)
  478.         subscribe(&fullVoxels, newvox);
  479.     subscribe(newvox, indiv);
  480.     } else {
  481.     fprintf(stderr, "newVoxPosition: can't find vox for [%d,%d,%d]\n",
  482.             newpos->x, newpos->y, newpos->z);
  483.     }
  484.     return newvox;
  485. }
  486.  
  487.     /*
  488.      *  Do a turtle walk of the voxels starting at vox,
  489.      *  using path, calling doit(vox, arg) for each vox reached
  490.      *  by a lower case letter.
  491.      */
  492. voxTurtle(vox, path, viewVector, doit, arg)
  493.     voxel *vox;
  494.     char *path;
  495.     point *viewVector;
  496.     int (*doit)();
  497.     char *arg;
  498. {
  499.     dimdir order[NDIMENSIONS];
  500.     char *pp;
  501.     int dim, dir, call_doit, halt_flag = 0;
  502.  
  503.     initOrder(order);
  504.     getOrder(order, (int *)viewVector);
  505.     for (pp = path; *pp; pp++) {
  506.     switch(*pp) {
  507.     case 'f':
  508.         call_doit = TRUE;
  509.         dim = order[2].dim;
  510.         dir = order[2].dir;
  511.         break;
  512.     case 'b':
  513.         call_doit = TRUE;
  514.         dim = order[2].dim;
  515.         dir = ~order[2].dir & 01;
  516.         break;
  517.     case 'l':
  518.         call_doit = TRUE;
  519.         dim = order[1].dim;
  520.         dir = order[1].dir;
  521.         break;
  522.     case 'r':
  523.         call_doit = TRUE;
  524.         dim = order[1].dim;
  525.         dir = ~order[1].dir & 01;
  526.         break;
  527.     case 'u':
  528.         call_doit = TRUE;
  529.         dim = order[0].dim;
  530.         dir = order[0].dir;
  531.         break;
  532.     case 'd':
  533.         call_doit = TRUE;
  534.         dim = order[0].dim;
  535.         dir = ~order[0].dir & 01;
  536.         break;
  537.     case 'F':
  538.         call_doit = FALSE;
  539.         dim = order[2].dim;
  540.         dir = order[2].dir;
  541.         break;
  542.     case 'B':
  543.         call_doit = FALSE;
  544.         dim = order[2].dim;
  545.         dir = ~order[2].dir & 01;
  546.         break;
  547.     case 'L':
  548.         call_doit = FALSE;
  549.         dim = order[1].dim;
  550.         dir = order[1].dir;
  551.         break;
  552.     case 'R':
  553.         call_doit = FALSE;
  554.         dim = order[1].dim;
  555.         dir = ~order[1].dir & 01;
  556.         break;
  557.     case 'U':
  558.         call_doit = FALSE;
  559.         dim = order[0].dim;
  560.         dir = order[0].dir;
  561.         break;
  562.     case 'D':
  563.         call_doit = FALSE;
  564.         dim = order[0].dim;
  565.         dir = ~order[0].dir & 01;
  566.         break;
  567.     default:
  568.         call_doit = 2;
  569.         break;
  570.     }
  571.     if (call_doit == 2)
  572.         continue;
  573.     vox = (voxel *)vox->dim[dim] [dir];
  574.     if (!vox)
  575.         break;
  576.     if (call_doit)
  577.         halt_flag = doit(vox, arg, pp);
  578.     if (halt_flag)
  579.         break;
  580.     }
  581. }
  582.  
  583. initOrder(order)
  584.     dimdir *order;
  585. {
  586.     int i;
  587.  
  588.     for(i = 0; i < NDIMENSIONS; i++) {
  589.     order[i].dim = i;
  590.     order[i].dir = NEXT;
  591.     }
  592. }
  593.  
  594. getOrder(order, viewVec)
  595.     dimdir *order;
  596.     int *viewVec /* an NDIMENSIONed vector */;
  597. {
  598.     int i, j, tmp;
  599.     /* sort */
  600.     for(i = 0; i < NDIMENSIONS; i++) {
  601.     for(j = i+1; j < NDIMENSIONS; j++) {
  602.         if(abs(viewVec [order[j].dim]) < abs(viewVec [order[i].dim]))
  603.         {
  604.         tmp = order[i].dim;
  605.         order[i].dim = order[j].dim;
  606.         order[j].dim = tmp;
  607.         }
  608.     }
  609.         /* get direction */
  610.     order[i].dir = (viewVec[order[i].dim] <= 0);
  611.     }
  612. }
  613.